A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
The invention disclosed herein relates to network configuration protocols and, in particular, to improved configuration protocols and methods for facilitating rapid traffic recovery following a link failure while still preventing loops from occurring in ring topologies.
Two basic requirements for computer networks are the availability of redundancy and the prevention of loops. Redundancy is needed so that a fault or break in a device or path in the network does not cut off traffic flow in the network. Loops occur when a network has multiple active paths between devices at any given time, resulting in the duplication of messages. Loops are prevented by keeping only one path between devices active at any given time. Since both redundancy and loop prevention involve configuration and selection of active and inactive paths, a network must carefully manage the states of its paths to meet both needs.
One solution to the problem of providing redundancy while preventing loops is the spanning tree algorithm or protocol. The spanning tree protocol, defined in IEEE 802.1, is used by bridges in a network to dynamically discover a subset of the network topology that provides path redundancy while preventing loops. Spanning tree protocol provides redundancy by defining a single tree that spans the bridges and maintaining all other paths and connections in a standby or blocked state. The protocol allows bridges to transmit messages to one another that allow each bridge to select its place in the tree and which states should be applied to each of its ports to maintain that place. For example, a port in a given bridge that is connected to an active path at a given time is kept in a forwarding state, in which all data traffic is received and transmitted to the next portion of the network, and a port in the bridge that is connected to an inactive path is kept in a non-forwarding state such as a blocking state in which traffic is blocked through that port.
In particular, bridges in a spanning tree network pass bridge protocol data units, or BPDUs, to one another which contain information including root, bridge and port identifiers and path cost data. This information is used by the bridges, among other things, to xe2x80x9celectxe2x80x9d one of the bridges in the spanning tree network to be a unique root bridge for the network, to calculate the shortest, least cost path from each bridge to the root bridge, to select which ports will be blocking, and for each LAN, elect one of the bridges residing in the LAN to be a designated bridge. In brief, the election of a root is performed by each bridge initially assuming itself to be the bridge, each bridge transmitting root BPDUs, each bridge comparing its BPDU information with that received from other bridges, and each bridge deciding whether to stop serving as a root and stop transmitting BPDUs when the configuration of another bridge as root is better than this bridge serving as root. Ports being converted from blocking to forwarding states and back again undergo several possible transition states depending upon the BPDUs received. Once the bridges have all reached their decisions, the network stabilizes or converges, and is eventually loop-free. A similar process is followed after a link failure has occurred in the network, in which case a new root and/or new active paths must be found.
The spanning tree algorithm presents several difficulties, particularly for large networks such as metropolitan area or wide area networks. The spanning tree protocol requires each bridge to perform complex calculations and comparisons related to path costs, which requires substantial processing resources and time. In addition, convergence under the spanning tree algorithm does not occur until all bridges have exchanged messages and evaluated the path costs. Thus, spanning tree has a relatively high convergence time and requires the use of heavy computing resources. Moreover, spanning tree has a seven bridge topology limitation. Thus, spanning tree protocol reduces performance in, and is not entirely adequate for use with, large networks such as MANs and WANs.
Other existing protocols, such as the health check mechanism available in devices offered by, for example, Extreme Networks, provide simplistic fault recovery solutions for use in very basic network configurations. However, no mechanism is available to the best of the inventors"" knowledge for allowing such simple solutions to be extended to more complex network configurations, except through the use of spanning tree protocol as discussed above. There is therefore a need for alternative network configuration solutions which provide redundancy and loop free operation but which use minimal computing resources and converge quickly even when used in large networks.
The present invention provides a network configuration protocol and algorithm which resolves deficiencies with prior protocols. The present invention relies on the appreciation that a large network having many bridges may be built as a combination of smaller networks, many of which may each be arranged in a ring topology. Because ring topology configuration is predetermined, a shorter configuration control packet protocol may be used for each ring to manage redundancy and loop free operation. In addition, each ring may be controlled by a single master bridge, selected for example by a system administrator, and each other bridge in the ring need not and does not make decisions with respect to its status. Finally, only the master bridge needs to change the status of its ports to effect redundancy. Thus, the use of computing resources in each ring and in the network as a whole is kept to a minimum, and redundancy is provided with minimal looping and extremely rapid convergence times.
Thus, in accordance with the invention, a ring loop free topology is achieved by means of selectively blocking and unblocking data traffic in one of the ring ports of a single master bridge for the ring. All other bridges in the ring keep their ports in non-blocked states. In multiple ring topologies, each ring has a single master bridge which chooses one of its ports to be blocking. In case of any link failure inside a given ring, the master bridge quickly detects the failure and automatically changes its blocking port to a non-blocking state in which traffic may flow and follow an alternate path, avoiding the failed link. When a failed link gets restored, the master bridge quickly detects the link restoration and converts its port back to a blocking state to avoid a loop from occurring. Since each ring in the network governs its own link redundancy and loop avoidance, each ring may be connected to other rings or other network environments running other protocols, including spanning tree protocols or other proprietary protocols.
To support large network configurations consisting of connected rings, the invention provides methodologies and data fields in the control packet protocol for coordinating control between connected rings. When two rings are connected through a shared link formed between two shared bridges, e.g., bridges which have ports belonging to the two connected rings, at least one of the rings carries the control packets being forwarded around the other ring. In some embodiments, the ring having the higher priority as between the two connected rings carries the control packets of the lower priority ring. The control packets are preferably marked as native to the lower priority ring, and thus foreign to the higher priority ring, before they are forwarded on to the higher priority ring.
In the event of failure of the shared link, the two connected rings form one large ring. Since the control packets for the lower priority ring are circulating around the entire ring, it does not detect the failure and thus keeps its blocking port from going into a forwarding state. Since the control packets for the higher priority ring do not circulate the entire larger ring, the master bridge for the higher priority ring detects the failure of the shared link and converts its blocking port to a forwarding state to provide fault recovery for the larger shared ring. In effect, the master bridge for the higher priority ring retains responsibility for providing fault recovery and loop free operation for the larger, combined ring.
Thus, in accordance with one aspect, the invention provides a method for coordinating control of fault recovery between connected rings in a network, each ring being assigned a priority value different than priority values of other connected rings. The method involves monitoring health of each ring through the use of control packets regularly transmitted and expected to be received by a master bridge of each ring, the master bridge converting one of its ports from a blocking state to a non-blocking state if a control packet is not received within an expected time delay from transmission. The method further includes each ring forwarding control packets belonging to the ring and any other connected ring having lower priority than the ring. When the network has at least one shared link between two connected rings, the method includes, if the shared link fails, forming a single ring from the two connected rings and the master bridge for the ring having the highest priority monitoring health of the formed single ring.
In accordance with another aspect of the invention, a method is described herein for use in a network topology comprising a plurality of rings, each ring having a plurality of bridges each having a plurality of ports, two of which ports belong to the respective ring. One of the plurality of bridges in each ring serves as a master bridge for the ring, the master bridge having a first port belonging to the first ring which is convertible between a blocking state and a non-blocking and a second port being maintained in a non-blocking state. All ports for other bridges belonging to each ring other than the master bridge are maintained in non-blocking states.
The inventive method according to this aspect of the invention facilitates rapid traffic recovery while avoiding loops, and involves regularly transmitting first control packets from a first master bridge onto a first ring, the first control packets each including a first ring identifier identifying the first ring, and regularly transmitting second control packets from a second master bridge onto a second ring, the second control packets each including a second ring identifier identifying the second ring. The one or more other bridges in the first ring forward the first control packets and, when available to the first ring, any second control packets. If any first or second control packet is not received by the convertible blocking port for the first or second master bridge, respectively, within a set delay time from transmission of such first or second control packet, then the convertible port for the first or second master bridge, respectively, is converted from a blocking state to a non-blocking state. This opens that port up for traffic, thus compensating for a fault in the ring which occurred and caused the delay in receipt of the respective control packet.
If the first master bridge convertible port receives one or more subsequent first control packets while in a non-blocking state, and the number of subsequent first control packets received equals or exceeds a set threshold number, the master bridge convertible port is converted from a non-blocking state back to a blocking state. The set threshold may be one or may be more than one, in which case the master bridge counts the number of control packets received for comparison to the set threshold. This prevents a loop from forming when the failed link is restored, as determined by the timely receipt of the subsequent control packet.
In some embodiments, the control packets include a topology change flag. The first or second master bridge sets the topology change flag in at least one control packet transmitted following conversion of the first or second master bridge first port from a blocking state to a non-blocking state or from a non-blocking state to a blocking state. The other bridges in the first and second rings each store bridging tables, and, upon receipt of a control packet having a set topology change flag, each of the other bridges flushes its stored bridging table.
The non-blocking state discussed herein may include a forwarding state, in which all data traffic including control packets are processed and forwarded. Alternatively, an additional, intermediary non-blocking state is provided in which data traffic continues to be blocked but control packets are processed and forwarded. This extra non-blocking state, referred to herein as a pre-forwarding state, allows for staged transitions from blocking to forwarding states while the master bridge determines more definitively whether it needs to go to a fully forwarding state. The pre-forwarding state also allows for time while other events in the ring which may impact on the fault are resolved. If any first or second control packet is not received by the first or second master bridge convertible port, respectively, within a second set delay time from transmission of such control packet from the first or second master bridge, then the master bridge convertible port is converted from a pre-forwarding state to a forwarding state.
In some configurations, at least one bridge is a shared bridge having a shared port belonging to both the first and second rings. The first ring has a higher priority than the second ring, and a port identifier is assigned to the shared port which matches the ring identifier for the first, higher priority ring. A second control packet received by a port in the shared bridge belonging to the second ring is marked, and, in each port of the shared bridge belonging to the second ring, a received marked control packet having a ring identifier which is the same as the port identifier of the port is de-marked. A received marked control packet having a ring identifier with a higher priority than the port identifier is dropped. These decisions facilitate circulation of control packets for lower priority rings around the higher priority rings, thus putting the higher priority rings in a position to assume control over fault recovery in the event of failure of the shared link.
In accordance with another aspect, the invention includes a computer readable medium storing a data structure defining a network configuration control packet protocol used by a ring topology in which each of a plurality of bridges has two ports belonging to a first ring. One of the bridges in the ring serves as a master bridge for the first ring, and a first master bridge port belonging to the first ring is maintained in a non-blocking state and a second master bridge port belonging to the first ring is convertible between a blocking state and one or more non-blocking states. The inventive control packet protocol includes, among other data fields, a ring identifier representing a value of a ring to which the control packet applies, a foreign status flag representing whether the control packet is native to the first ring or belongs to a second ring in the network and is thus foreign to the first ring, and a topology change flag settable by the master bridge upon conversion of the state of the master bridge second port. The control packet is used by the master bridge, in accordance with methodologies described herein, to indicate whether a traffic link has failed or been restored in the ring, to determine whether to convert the second port from one state to another, and to notify non-master bridges in the ring of conversion of the second port.
In some embodiments, the control packet further contains a master identifier representing the master bridge of the ring to which the control packet applies, a hello time field representing a time period in which the control packet is regularly sent by the master bridge, and a forwarding bit which is set by the master bridge to notify other bridges in the ring to go to a forwarding state from an intermediary or pre-forwarding state when, for example, the master bridge sets one of its ports to a blocking state.
In accordance with a further aspect of the invention, a network is described herein in which each of a plurality of bridges has two ports belonging to a first ring. The network comprises a master bridge in which a first port belonging to the first ring is maintained in one or more non-blocking states and a second port is convertible between a blocking state and one or more non-blocking states. The master bridge comprises transmission means for regularly transmitting first control packets onto the first ring, the control packets each including a ring identifier identifying the first ring. The network further contains one or more non-master bridges in which both ports belonging to the first ring are maintained in non-blocking states, the non-master bridges forwarding first control packets and second control packets belonging to a second ring connected to the first ring. A program means is provided in the master bridge for converting the convertible port from a blocking state to a non-blocking state if a first control packet is not received by the master bridge within a first delay time from transmission of such first control packet from the master bridge and for converting the convertible port from a non-blocking state to a blocking state if a first control packet is received by the second port within a second delay time from transmission of the first control packet from the master bridge first port.
In some embodiments, the network comprises means for distinguishing between first control packets belonging to the ring and second control packets belonging to the second ring. The means for distinguishing between first and second control packets may comprise a foreign status flag in the control packets which is set when a control packet belongs to the second ring, and may further include program code residing in the bridges in the first ring which, when executed, causes the bridges to detect the foreign status flag in each control packet and to determine whether each control packet belongs to the first or second ring.